package com.cg.leetcode;

import org.junit.Test;

import java.util.*;

/**
 * 841.钥匙和房间
 *
 * @program: LeetCode->LeetCode_841
 * @description: 841.钥匙和房间
 * @author: cg
 * @create: 2021-09-24 20:59
 **/
public class LeetCode_841 {

    @Test
    public void test841() {
        ArrayList<List<Integer>> rooms = new ArrayList<>();
        rooms.add(Arrays.asList(1, 3));
        rooms.add(Arrays.asList(3, 0, 1));
        rooms.add(Arrays.asList(2));
        rooms.add(Arrays.asList(0));
        //rooms.add(Arrays.asList(1));
        //rooms.add(Arrays.asList(2));
        //rooms.add(Arrays.asList(3));
        //rooms.add(Arrays.asList(0));
        System.out.println(canVisitAllRooms(rooms));
    }

    /**
     * 有 N 个房间，开始时你位于 0 号房间。每个房间有不同的号码：0，1，2，...，N-1，并且房间里可能有一些钥匙能使你进入下一个房间。
     * 在形式上，对于每个房间 i 都有一个钥匙列表 rooms[i]，每个钥匙 rooms[i][j] 由 [0,1，...，N-1] 中的一个整数表示，其中 N = rooms.length。 钥匙 rooms[i][j] = v 可以打开编号为 v 的房间。
     * 最初，除 0 号房间外的其余所有房间都被锁住。
     * 你可以自由地在房间之间来回走动。
     * 如果能进入每个房间返回 true，否则返回 false。
     * <p>
     * 示例 1：
     * 输入: [[1],[2],[3],[]]
     * 输出: true
     * 解释:
     * 我们从 0 号房间开始，拿到钥匙 1。
     * 之后我们去 1 号房间，拿到钥匙 2。
     * 然后我们去 2 号房间，拿到钥匙 3。
     * 最后我们去了 3 号房间。
     * 由于我们能够进入每个房间，我们返回 true。
     * <p>
     * 示例 2：
     * 输入：[[1,3],[3,0,1],[2],[0]]
     * 输出：false
     * 解释：我们不能进入 2 号房间。
     * <p>
     * 提示：
     * 1) 1 <= rooms.length <= 1000
     * 2) 0 <= rooms[i].length <= 1000
     * 3) 所有房间中的钥匙数量总计不超过 3000。
     *
     * @param rooms
     * @return
     */
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        //广度优先解决
        Deque<Integer> deque = new LinkedList<>();
        int n = rooms.size();
        boolean[] vis = new boolean[n];
        vis[0] = true;
        deque.offer(0);
        while (!deque.isEmpty()) {
            Integer pop = deque.pop();
            for (Integer i : rooms.get(pop)) {
                if (!vis[i]) {
                    vis[i] = true;
                    deque.offer(i);
                }
            }
        }
        for (boolean flag : vis) {
            if (!flag) {
                return false;
            }
        }
        return true;
    }
    /*public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        //深度优先解决
        int roomSize = rooms.size();
        boolean[] dist = new boolean[roomSize];
        dfs(rooms, dist, 0);
        for (boolean flag : dist) {
            if (!flag) {
                return false;
            }
        }
        return true;
    }

    private void dfs(List<List<Integer>> rooms, boolean[] dist, int index) {
        if (dist[index]) {
            return;
        }
        dist[index] = true;
        for (Integer i : rooms.get(index)) {
            dfs(rooms, dist, i);
        }
    }*/
}
